C/C++ Users Group Library 1996 July/C-C++ Users Group Library July 1996.iso/vol_200/275_01/lcau.doc

Text File | 1980-01-01 | 15KB | 283 lines

LCAU.DOC

This disk is a supplement to the disk "LCA.C" which was released in
Summer, 1987. The original disk contained 9 programs written in "C" to
calculate and display the evolution of linear cellular automata.
Although the programs represented a point in the evolution of the
course Fortran III offered during the past several semesters, and were
promoted at the XVI Feria de Puebla, they also had a strong
inspiration in an article in the December, 1986, issue of Byte magazine
which explained how cellular automata could lead to interesting
abstract mathematical art.

    Kenneth E. Perry, Abstract mathematical art, Byte,
    December 1986, pages 181-192.

The 9 programs in the LCAkr.C set ran through the range of 2, 3, and 4
states per cell, as well as interactions between first, second, or
third neighbors. The combinations (4,1) and (4,2) are probably the most
colorful, but the binary first neighbor version (2,1) is more amenable
to an exhaustive analysis.

Programs in the new series are named LCAU to distinguish them from
members of the old series.

In the old series, In all cases except for (2,1), only totalistic rules
were considered. Totalistic rules are those for which the transition
depends only on the number of cells of different kinds in each
neighborhood, but not on their precise arrangement. More exactly, each
state gets assigned an integer in the range 0 to k-1 as a weight, the
actual transition being a function of the weighted sum of all the
neighbors (including the evolving cell). The artistic effects arise
from assigning colors to each of cell values.

Although the use of totalistic rules serves to reduce the enormous
number of possible automata greatly, it excludes many interesting
possiblilities arising from a more detailed specification of the
evolutionary rules. When k, the number of states per cell is small,
there is not too much which is possible in the way of design, but once
it reaches 4 or beyond some interesting constructions become possible.
LCA41.C in particular, contains enhanced rule and line editing menus
which allow experimentation with the design of rules.

Certain of the demonstrations in LCAU41.C show how the design process
can be used. There is an example of a "binary counter'" which consists
of a glider gun together with bistable targets. In one state the target
absorbs the glider and changes to the other state. In the second state
the target passes the glider, reverting to the first state. Thus half
the gliders are lost to each target, whose state forms a binary counter
whose carry is represented by the gliders which are allowed to pass.

Another demonstration shows how a bouncing glider may shuttle between
two obstacles - still lifes - drawing them ever closer together. Just
as the glider is about to be crushed, the walls coalesce but the glider
escapes to one side, seeking new walls to conquer. Multiple gliders may
go about their business, competing for the wall if they lie on opposite
sides or hastening the squeeze if they lie on the same side.

A third demonstration shows a slow glider propelled by an intrenal
glider or gliders bouncing back and forth - a sort of Mexican jumping
bean. When a fast glider overtakes a slower glider, they coalesce,
producing an even slower glider.

A fourth demonstration shows gliders of two different velocities, which
can be used to set up a remote still life whose reaction to further
gliders gives it a life of its own.

Such constructions can be used to generate interesting patterns, but
they also serve theoretical ends as well. For example, the binary
counters establish the existence of structures with both exponentially
long transients and exponentially long cycles. Since they still use
several cells to establish the basic components and their spacings,
they still do not reach theoretical maxima; but they do lie within
certain factors of such maxima.

When k becomes larger still, universal Turing machines can be
programmed, but this probably requires a k of at least 6 or 8.

Another extensive addition which has been made to the programs is to be
found in the series PROB.C, which can be invoked by typing "t" in the
main menu (the old totalistic rule number can still be utilized by
typing "T"); in fact their inclusion more than doubles the size of the
programs. These new programs permit a statistical survey of the
properties of the automaton. Originally they calculated simple
probabilities on the basis of ideas which go by the name of "mean field
theory," whose results were plausible but not entirely convincing.

Since then two interesting articles have appeared [the second as a
preprint]:

    W. John Wilbur, David J. Lipman and Shihab A. Shamma, On the
    prediction of local patterns in cellular automata, Physica
    19D 397-410 (1986).

    Howard A. Gutowitz, Jonathan D. Victor and Bruce W. Knight,
    Local structure theory for cellular automata, Physica 28D
    18-48 (1987).

These articles, from differing points of view, show how to take
correlations between cells into account by calculating the
probabilities of strings of cells. Rather than taking individual
probabilties as fundamental and deducing the probabilities of
combinations, the process is inverted; self consistent probabilities
for strings (or blocks) of a certain length are found from which the
probabilities of individual cells are obtained by averaging.

The calculations of these articles have been included among the options
of the "t" submenu, so that probabilities derived from blocks of length
up to 6 can be compared with simpler estimates and with the actual
performance of the automaton.

A third feature of the new series is the incorporation of the de Bruijn
diagrams within the main program, together with a visual representation
in terms of chords of a circle. It is still not possible to transfer
the cycles obtained back to the main program without copying them on
paper and editing the initial line with the option "l". Limitations of
space and time severely restrict the lengths of periods which can be
analyzed. Although interesting gliders and cycles are found within the
accessible range of the program, there are many others of longer
periods which manifest themselves experimentally when the evolutions
are run. It would be nice if the exhaustive analysis afforded by the
de Bruijn diagrams were feasible for the longer periods that show up on
the screen, but they would really require a faster computer, more
memory, and probably programs incorporating finer details of the
algorithms used.

The programs contain a bare minimum of help facilities, in the sense
that menus of one type or another are presented at various stages in
the evolution of the programs, and others are sometimes available by
typing a question mark, just as a slash will often clear portions of
the screen.

A manual consisting of the lecture notes for Fortran III is in
preparation, for which chapters are planned describing the accompanying
programs. As is well known, the preparation of manuals always lags the
evolution of the programs which they are supposed to describe.

There are still some interesting problems of presentation - recall that
Fortran III is supposed to be dedicated to graphical techniques!
Presentation of simple evolution is easily solved, since the resolution
and velocity of the graphics controllers included as standard equimpent
in IBM PC's and clones is adequate. Unfortunately color monitors and
their controllers are sometimes seen as premium equipment which was not
included in a given installation, so that a monochromatic rendering of
the color displays must be endured.

Even so, the speed and screen resolution which is available in the
present generation of equipment is only marginally satisfactory, having
only a fraction of the resolution of pen and ink plotters which have
been commonly available. Once statistics pertaining to the evolution of
automata are to be presented,